package com.xiayuanxing.arithmetic.DataStructures.Sort;

import java.util.Arrays;

/**
 * @program: arithmetic
 * @description: 希尔排序
 * @author: xia yuan xing
 * @create: 2021-09-24 16:25
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] array = {8,9,1,7,2,3,5,4,6,0};
//        shellSort(array);
//        shellSort1(array);
//        shellSort2(array);
        shellSort3(array);
    }


    /**
     * 希尔排序
     * 写法一：
     *
     * @param array
     */
    public static void shellSort(int[] array) {
        for (int step = array.length / 2; step > 0; step /= 2) {
            for (int i = step; i < array.length; i++) {
                int value = array[i];
                int j;
                for (j = i - step; j >= 0 && array[j] > value; j -= step) {
                    array[j + step] = array[j];
                }
                array[j + step] = value;
            }
        }
        System.out.println(Arrays.toString(array));
    }


    /**
     * 写法二：交换式
     *
     * @param array
     */
    public static void shellSort1(int[] array) {
        int temp = 0;
        for (int step = array.length / 2; step > 0; step /= 2) {

            for (int i = step; i < array.length; i++) {
                //遍历各组中所有的元素（共step组，每组有几个数据），步长step
                for (int j = i - step; j >= 0; j -= step) {

                    //如果当前元素大于加上步长后的那个元素，说明交换
                    if (array[j] > array[j + step]) {
                        temp = array[j];
                        array[j] = array[j + step];
                        array[j + step] = temp;
                    }

                }
            }
        }

        System.out.println("输出："+Arrays.toString(array));
    }


    /**
     * 写法三：逐步推导
     *
     * @param array
     */
    public static void shellSort2(int[] array) {

        int temp = 0;
        //第一轮排序，将十个数组分成五组处理
        for (int i = 5; i < array.length; i++) {
            //遍历各组中所有的元素（共5组，每组有两个数据），步长5
            for (int j = i - 5; j >= 0; j -= 5) {

                //如果当前元素大于加上步长后的那个元素，说明交换
                if (array[j] > array[j + 5]) {
                    temp = array[j];
                    array[j] = array[j + 5];
                    array[j + 5] = temp;
                }

            }
        }
        System.out.println("一轮后输出："+Arrays.toString(array));


        //第二轮排序，将十个数组分成5/2=2组处理
        for (int i = 2; i < array.length; i++) {
            //遍历各组中所有的元素（共5组，每组有两个数据），步长2
            for (int j = i - 2; j >= 0; j -= 2) {

                //如果当前元素大于加上步长后的那个元素，说明交换
                if (array[j] > array[j + 2]) {
                    temp = array[j];
                    array[j] = array[j + 2];
                    array[j + 2] = temp;
                }

            }
        }
        System.out.println("二轮后输出："+Arrays.toString(array));


        //第三轮排序，将十个数组分成5/2/2=1组处理
        for (int i = 1; i < array.length; i++) {
            //遍历各组中所有的元素（共5组，每组有两个数据），步长1
            for (int j = i - 1; j >= 0; j -= 1) {

                //如果当前元素大于加上步长后的那个元素，说明交换
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }

            }
        }
        System.out.println("三轮后输出："+Arrays.toString(array));

    }



    /**
     * 写法四：移位式
     *
     * @param array
     */
    public static void shellSort3(int[] array) {

        for (int step = array.length / 2; step > 0; step /= 2) {
            for (int i = step; i < array.length; i++) {
                int j = i;
                int temp = array[j];
                if (array[j] < array[j - step]){
                    while (j - step >= 0 && temp < array[j - step]){
                        //移动
                        array[j] = array[j - step];
                        j -= step;
                    }
                    //当退出while循环后，就给temp找到插入的位置
                    array[j] = temp;
                }

            }
        }

        System.out.println("输出："+Arrays.toString(array));
    }




}